package DynamicProgrammingPackage;

/**
 * @author Lzm
 * @version 1.0
 */
public class findTargetSumWays_ {
  public static void main(String[] args) {
    int[] nums = new int[]{1,1,1,1,1};
    System.out.println(findTargetSumWays(nums, 3));
  }

  // 思路: 将nums分为两个集合: addArr和subArr 使得addArr + subArr = sum && addArr - subArr = target
  // 得出addArr = (target + sum) / 2, 即转为背包问题, 问一个容量为n的背包有多少种方式装满
  // 1. dp[j]表示容量为j的背包将其装满有dp[j]种方式
  // 2. 递推公式:
  // 若有物品重量为1, 则有dp[4]种方法凑成dp[5]
  // 若有物品重量为2, 则有dp[3]种方法凑成dp[5]
  // 若有物品重量为3, 则有dp[2]种方法凑成dp[5]
  // 若有物品重量为4, 则有dp[1]种方法凑成dp[5]
  // 若有物品重量为5, 则有dp[0]种方法凑成dp[5]
  // 故的dp[j] = dp[j - num[i]]
  // 3. 初始化 dp = 0;
  // 4. 遍历顺序: 先正向遍历物品再得倒序遍历背包
  public static int findTargetSumWays(int[] nums, int target) {
    int sum = 0;
    for (int num : nums) {
      sum += num;
    }
    if (Math.abs(target) > sum) return 0;
    if((target + sum) % 2 == 1) return 0;
    int bagSize = (sum  + target) / 2;
    int[] dp = new int[bagSize + 1];
    dp[0] = 1;
    for (int i = 0 ; i < nums.length ; i++){
      for (int j = bagSize ; j >= nums[i] ; j--){
        dp[j] += dp[j - nums[i]];
      }
    }
    return dp[bagSize];
  }
}
